package com.leetcode.双周赛.第48场;

import java.util.Arrays;
import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;

/**
 * @author: xiaomi
 * @date: 2021/3/20
 * @description: 5712. 你能构造出连续值的最大数目
 * https://leetcode-cn.com/contest/biweekly-contest-48/problems/maximum-number-of-consecutive-values-you-can-make/
 * 在竞赛里碰到这种没有思路的题目时，可能就需要去模拟一下，然后找到能用程序实现的方案去落实！！！
 * 要求从 0 开始返回
 */
public class B_5712_你能构造出连续值的最大数目 {

	static B_5712_你能构造出连续值的最大数目 action = new B_5712_你能构造出连续值的最大数目();

	public static void main(String[] args) {
		test1();
		test2();
		test3();
		test4();
	}


	public static void test1() {
		//2
		int[] coins = new int[]{1, 3};
		int res = action.getMaximumConsecutiveByDPFromZero(coins);
		System.out.println("res = " + res);
	}

	public static void test2() {
		//8
		int[] coins = new int[]{1, 1, 1, 4};
		int res = action.getMaximumConsecutiveByDPFromZero(coins);
		System.out.println("res = " + res);

	}

	public static void test3() {
		//20
		int[] coins = new int[]{1, 4, 10, 3, 1};
		int res = action.getMaximumConsecutiveByDPFromZero(coins);
		System.out.println("res = " + res);
	}

	public static void test4() {
		//2
		int[] coins = new int[]{1, 3, 4};
		int res = action.getMaximumConsecutiveByDPFromZero(coins);
		System.out.println("res = " + res);
	}


	/**
	 * 以我的设计思路，先求出前缀和，然后间隔依次增大的方式，填入记录数组，最后判断数组。
	 * 从枚举的例子来看，这个思路应该是可行的。
	 * 这种思路是有问题的！失落。
	 *
	 * @param coins
	 * @return
	 */
	public int getMaximumConsecutive(int[] coins) {
		int len = coins.length;
		int[] preFix = new int[len];
		preFix[0] = coins[0];
		for (int i = 1; i < len; i++) {
			preFix[i] = preFix[i - 1] + coins[i];
		}

		int size = preFix[len - 1] + 1;
		boolean[] recorder = new boolean[size];
		recorder[0] = true;
		for (int i = 0; i < len; i++) {
			recorder[coins[i]] = true;
			recorder[preFix[i]] = true;
		}
		int interval = 2;
		int nextIndex = 0;
		while (interval < len) {
			for (int i = 0; i < len; i++) {
				nextIndex = i + interval;
				if (nextIndex < len) {
					recorder[preFix[nextIndex] - preFix[i]] = true;
				} else {
					break;
				}
			}
			interval++;
		}
		//最后遍历 recorder
		int res = 0;
		int count = 0;
		for (int i = 0; i < size; i++) {
			if (recorder[i]) {
				count++;
			} else {
				res = Math.max(res, count);
				count = 0;
			}
		}
		res = Math.max(res, count);
		return res;
	}

	/**
	 * 这种题目需要
	 * 使用一个集合set 和链表（只有遍历和添加操作，不需要删除，所以我选择 linkedList,、
	 * 但是又需要添加新的元素，那么只好选择双端队列了）
	 * ---
	 * 感觉能解出来，但是会超时。不过思路是对的，只要根据 从 0 的下标进行优化算法方案即可。
	 *
	 * @param coins
	 * @return
	 */
	public int getMaximumConsecutiveByDP(int[] coins) {
		Arrays.sort(coins);
		int min = coins[0];
		if (min != 1) {
			return 1;
		}
		int len = coins.length;
		int sum = coins[0];
		for (int i = 1; i < len; i++) {
			sum += coins[i];
		}
		//init set
		//定义 set 为遍历 coins 时当时所能找到的最多的硬币的数量和的集合
		HashSet<Integer> set = new HashSet<>();
		Deque<Integer> list = new LinkedList<>();
		set.add(min);
		list.add(min);
		int tempValue = 0;
		for (int i = 1; i < len; i++) {

			int size = list.size();
			while (size > 0) {
				Integer temp = list.removeFirst();
				tempValue = temp + coins[i];
				if (!set.contains(tempValue)) {
					list.addLast(tempValue);
					set.add(tempValue);
				}
				list.addLast(temp);
				size--;
			}
			//最后处理 coins[i] 的值
			if (!set.contains(coins[i])) {
				list.addLast(coins[i]);
				set.add(coins[i]);
			}
		}
		//最后判断连续性
		//原来题目要求的是从 0 开始
		int res = 0;
		int resMin = min, len1 = -1;
		int tempLen = 2;
		for (int i = min + 1; i <= sum; i++) {
			if (set.contains(i)) {
				tempLen++;
			} else {
				return tempLen;

				//出现中断
//				res = Math.max(res, tempLen);
//				if (len1 == -1 && resMin == 1) {
//					len1 = tempLen;
//				}
//				tempLen = 0;
			}
		}
//		res = Math.max(res, tempLen);
//		if (resMin == 1 && (len1 == res || len1 == -1)) {
//			//如果刚好是从1开始为最长
//			return res + 1;
//		}
		return tempLen;
	}

	/**
	 * 排序一遍以后就容易发现规律：
	 * 第一个数必须是1，否则直接断开；
	 * 到了第二个数，观察左边的连续数字：0，1。假设此时 ni=3，那么即使 0+3=3 无法得到2 ，此时断开。
	 * 同理，就能发现：当 ni- preFix(ni-1)>1 时，就无法完成连续数字。
	 *
	 * @param coins
	 * @return
	 */
	public int getMaximumConsecutiveByDPFromZero(int[] coins) {
		Arrays.sort(coins);
		if (coins[0] != 1) {
			return 1;
		}
		int len = coins.length;
		int prefixSum = 1;
		for (int i = 1; i < len; i++) {
			if (coins[i] - prefixSum > 1) {
				//此时已经断开
				break;
			} else {
				prefixSum += coins[i];
			}
		}
		return prefixSum+1;
	}
}
